//
// Created by 高森森 on 2022/2/12.
//

#ifndef LEETCODE_SOLUTION38_H
#define LEETCODE_SOLUTION38_H
#include<iostream>
#include<vector>
#include<bitset>
#include<queue>
#include <tuple>

using namespace std;

class Solution38 {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        const int n=graph.size();
        queue<tuple<int,bitset<12>,int>>que;
//        bitset<12>visited[n];
        vector<vector<int>> seen(n, vector<int>(1 << n));
        for(int i=0;i<n;i++){
            bitset<12>b{0};
            b.set(i);
            seen[i][1<<i]= true;
            que.emplace(i,b,0);
        }
        int ans=0;
        while(!que.empty()){
            auto[u,mask,dist]=que.front();
            que.pop();
            if(mask.count()==n){
               ans=dist;
               return ans;
            }
            for(int v:graph[u]){
                auto m=mask;
                 int mask_v=(int)m.set(v).to_ulong();
                if(!seen[v][mask_v]){
                    que.emplace(v,mask_v,dist+1);
                    seen[v][mask_v]= true;
                }
            }
        }
        return ans;
    }
};


#endif //LEETCODE_SOLUTION38_H
